{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Binary Search Tree Check \n",
    "\n",
    "## Problem Statement\n",
    "\n",
    "Given a binary tree, check whether it’s a binary search tree or not.\n",
    "\n",
    "** Again, no solution cell, just worry about your code making sense logically. Hint: Think about tree traversals. **\n",
    "\n",
    "## Solution\n",
    "\n",
    "Fill out your solution below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "class TreeNode(object):\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def isValidBST(self, root):\n",
    "        return self.is_valid(root, -math.inf, math.inf)\n",
    "    \n",
    "    def is_valid(self, root, min_val, max_val):\n",
    "        if root is None:\n",
    "            return True\n",
    "        else:\n",
    "            return ( root.val > min_val and root.val < max_val and\n",
    "                self.is_valid(root.left, min_val, root.val) and\n",
    "                self.is_valid(root.right, root.val, max_val) )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is a classic interview problem, so feel free to just Google search \"Validate BST\" for more information on this problem!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
